
/**树Map，键为字符，值为树节点 */
type TrieMap = Map<string, TrieNode>
/**前缀树的节点类型元组，第一个是Map，若有结果，则第二个为结果  (也就是元组长度为2时，代表有结果) */
type TrieNode = [TrieMap] | [TrieMap, string]

/**208. 实现 Trie (前缀树) */
export function Trie208() {
    class Trie {
        root: TrieNode
        constructor() {
            this.root = [new Map()]
        }

        insert(word: string): void {
            let node = this.root
            for (let i = 0; i < word.length; i++) {
                const c = word[i]
                const map = node[0]
                if (!map.has(c)) {
                    map.set(c, [new Map()])
                }
                node = map.get(c)!
            }
            if (node.length < 2) node[1] = word //叶子结点记录单词
        }

        search(word: string): boolean {
            let node = this.root
            for (let i = 0; i < word.length; i++) {
                const c = word[i]
                const map = node[0]
                if (map.has(c)) {
                    node = map.get(c)!
                } else return false
            }
            if (word === node[1]) return true
            return false
        }

        startsWith(prefix: string): boolean {
            let node = this.root
            for (let i = 0; i < prefix.length; i++) {
                const c = prefix[i]
                const map = node[0]
                if (map.has(c)) {
                    node = map.get(c)!
                } else return false
            }
            return true
        }
    }

    // ——————————入参测试
    const trie = new Trie()
    const fnNames: (Exclude<keyof Trie, 'root'>)[] = ["insert", "search", "search", "startsWith", "insert", "search"]
    const inputs: string[][] = [["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
    inputs.forEach(([word], i) => {
        const fnName = fnNames[i]
        const res = trie[fnName](word)
        console.log(`第${i}次调用`, `trie.${fnName}('${word}') \t = \t ${res}`);
        // console.log(deepClone(trie.root));
    })
}
